package leetcode_500;

/**
 *@author 周杨
 *CircularArrayLoop_457 判断数组里是否成环
 *describe:用快慢指针做 AC 32%
 *2018年8月25日 下午2:38:48
 */
public class CircularArrayLoop_457 {
	public static void main(String[] args) {
		CircularArrayLoop_457 test=new CircularArrayLoop_457();
		test.circularArrayLoop1(new int[] {-2,1,-1,-2,-2});
	}
	
	int[] arr;
    public boolean circularArrayLoop(int[] nums) {
        arr = nums;
        for (int i=0; i<nums.length; i++) {
            if (nums[i] == 0) continue;
            //two pointers
            int j=i, k=shift(i);
            while (nums[i]*nums[k]>0 && nums[i]*nums[shift(k)]>0) {
                if (j == k) {
                    // check for loop with only one element
                    if (j == shift(j)) break;
                    return true;
                }
                j = shift(j);
                k = shift(shift(k));
            }
            // loop not found, set all element along the way to 0
            j = i;
            int val = nums[i];
            while (nums[j]*val > 0) {
                int next = shift(j);
                nums[j] = 0;
                j = next;
            }
        }
        return false;
    }
    
    public int shift(int pos) {
        return (pos+arr[pos]+arr.length) % arr.length;
    }
	
	/**
	 * describe:没有考虑到 后面成环的情况 独自成环
	 * 2018年8月25日 下午2:36:02
	 */
	public boolean circularArrayLoop1(int[] nums) {
		boolean dp[]=new boolean[nums.length];
		int len=nums.length;
		for(int i=0;i<nums.length;++i) {
			if(dp[i])
				continue;
			int index=i;
			boolean flag=false;
			while(nums[index]*nums[(index+nums[index]+len)%len]>0) {
				if(index==i) {
					if(flag) {//是否是第一次
						if((index+nums[index])%len==i) {//中间没元素
							dp[index]=true;
							help(i, index, dp, nums);
							break;
						}
						else
							return true;
					}
					else {
						flag=true;
						index=(index+nums[i]+len)%len;
					}
				}
				else {
					index=(index+nums[index]+len)%len;
				}
			}
			//在里面还能出来 说明此时方向不对了
			dp[i]=true;
			help(i,index,dp,nums);
		}
		return false;
    }
	
	private void help(int start,int end,boolean []dp,int nums[]) {
		while(start!=end) {
			dp[start]=true;
			start=((start+nums[start]+nums.length)%nums.length);
		}
	}
}
